//骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。 
//
// 给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (
//row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。 
//
// 如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。 
//
// 注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。 
//
// 
//
// 示例 1： 
// 输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13
//,2,7,22]]
//输出：true
//解释：grid 如上图所示，可以证明这是一个有效的巡视方案。
// 
//
// 示例 2： 
// 输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
//输出：false
//解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length == grid[i].length 
// 3 <= n <= 7 
// 0 <= grid[row][col] < n * n 
// grid 中的所有整数 互不相同 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 模拟 👍 19 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-13 09:16:18
 * @description 2596.检查骑士巡视方案
 */
public class CheckKnightTourConfiguration{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CheckKnightTourConfiguration().new Solution();
		  int [][]grid={{24,11,22,17,4},{21,16,5,12,9},{6,23,10,3,18},{15,20,1,8,13},{0,7,14,19,2}};
//		 int [][]grid={{8,3,6},{5,0,1},{2,7,4}};
		 System.out.println(solution.checkValidGrid(grid));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean checkValidGrid(int[][] grid) {
		int n = grid.length;
		if(grid[0][0]!=0) return false;
		return check(grid,n,0,0);
    }
	private boolean isValid(int[][] grid,int x,int y){
		return x>=0&&y>=0&x<grid.length&&y<grid.length;
	}
	private boolean check(int [][] grid,int n,int i,int j){
		int []dx={-1,-2,-2,-1,1,2,2,1};
		int []dy={-2,-1,1,2,2,1,-1,-2};
		for (int pos = 0; pos+1<n*n; pos++) {
			for (int k = 0; k < 8; k++) {
				int x=i+dx[k];
				int y=j+dy[k];
				if(isValid(grid,x,y)&&grid[x][y]==pos+1){
					i=x;
					j=y;
					break;
				}
			}
			if(pos+1!=grid[i][j]) return false;
		}
		return true;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
